package com.zjsru.oneDay202205;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: likew
 * @Date: 2022/5/22
 * 我能赢吗
 * 在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过  100 的玩家，即为胜者。
 *
 * 输入：maxChoosableInteger = 10, desiredTotal = 11
 * 输出：false
 * 解释：
 * 无论第一个玩家选择哪个整数，他都会失败。
 * 第一个玩家可以选择从 1 到 10 的整数。
 * 如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
 * 第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
 * 同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。
 *
 */
public class canIWin {
    Map<Integer,Boolean> memory = new HashMap<>();
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if((1 + maxChoosableInteger)*maxChoosableInteger*0.5 <desiredTotal){
            return false;
        }
        return  dfs(maxChoosableInteger,0,desiredTotal,0);
    }
    /**
     *
     * @param maxChoosableInteger 供选择的数
     * @param userNumbers  被选择的数，注意用二进制表示，可能比较难以理解。如0010则表示2已经被选择，0001则表示1已被选择
     * @param desiredTotal  累计整数合需要超过的目标值
     * @param currentTotals  当前累计整数合
     * @return
     */
    private boolean dfs(int maxChoosableInteger, int userNumbers, int desiredTotal,int currentTotals){
        if(!memory.containsKey(userNumbers)){
            boolean res = false;
            for (int i = 0; i < maxChoosableInteger; i++) {
                if(((userNumbers >> i) & 1) == 0){
                    if(i + 1 + currentTotals >= desiredTotal){
                        res = true;
                        break;
                    }
                    if(!dfs(maxChoosableInteger,userNumbers | (1<<i),desiredTotal,currentTotals + 1 + i)){
                        res = true;
                        break;
                    }
                }
            }
            memory.put(userNumbers,res);
        }
        return memory.get(userNumbers);
    }
    
    public static void main(String[] args) {
        canIWin canIWin = new canIWin();
        int maxChoosableInteger = 10;
        int desiredTotal = 11;
        System.out.println(canIWin.canIWin(maxChoosableInteger, desiredTotal));
    }
}
